package 算法.leetcode.labuladong.数组和链表;

/**
 * @author lchenglong
 * @date 2022/6/15
 */
public class 拼车 {
    class Solution {
        public boolean carPooling(int[][] trips, int capacity) {
            // 构建差分数组
            int[] nums = new int[1001];
            Difference df = new Difference(nums);
            for (int[] trip:trips){
                int val = trip[0];
                // 乘客上车站点
                int i = trip[1];
                // 乘客在该站点已下车
                int j = trip[2]-1;
                // [i,j]站点上车乘客的数量
                df.increment(i,j,val);
            }
            // 每个站点车上的人数
            int[] res =  df.result();
            // 检验是否超载
            for (int i=0;i<res.length;i++) {
                if (res[i]>capacity){
                    return false;
                }
            }
            return true;
        }
    }
}
